n=994;
S=[2,402,549,1244,1385,2328,2759,3479,4027,4259,4830,5008,5013,5503,6054,6320,6800,7221,7778,7995,8055,8604,8887,9338,9933,10453,11200,12049,12067,12580,13418,14298,15211,15915,16492,17265,17914,18641,19136,19334,20012,20079,20455,21139,21416,22062,22731,23488,23556,23783,24476,24605,25381,26076,26375,26467,26684,27449,28390,29343,29622,30121,30955,31866,32071,32202,32888,33742,34601,34783,35554,36092,37059,37925,38866,39111,39625,40237,40959,41260,41818,42234,42383,42438,42551,43000,43147,43196,44129,44936,44939,45153,45460,46297,46423,46935,47904,48716,48802,49350,50063,50920,51725,52407,53132,53880,54526,55484,55845,56214,57192,58111,58616,58745,59438,59775,60072,60912,61298,61529,61896,62004,62449,63124,63788,64079,64985,65338,65442,66435,67055,67873,68443,68870,69090,69386,69562,70428,71401,71657,72612,73565,74459,74920,75003,75592,76390,76489,76638,77541,77871,78388,79118,79613,79806,80201,80706,81524,81992,82601,83413,83502,83649,83752,84268,84354,84472,84883,85555,85648,86315,86943,86990,87553,87643,88491,89362,89969,90635,90656,90886,91601,92139,93099,93310,93760,94116,94832,95102,95645,95691,96492,97125,98036,98659,99527,100525,101267,101548,102219,103054,104002,104021,104622,104853,104962,105131,105234,105669,106504,107347,108012,108563,108664,109290,109772,110324,111025,111942,112483,112729,113692,113754,114352,114947,115633,116100,116413,116561,117028,118012,118714,119131,119853,120157,120524,121355,121547,121737,122722,122750,122784,123435,123733,123868,124864,125644,126050,126748,127447,128113,128776,129158,129887,130867,131844,131979,132428,132438,132440,133356,134069,134773,134826,135262,135271,135411,136397,137316,137646,138618,139565,139929,140272,141236,141454,141794,142259,142884,143642,144525,144536,144677,144943,145683,145806,146769,147363,147654,148627,149223,149431,150119,150139,151119,151244,151273,151394,152225,153173,153624,154428,155043,155577,155726,156307,156778,156986,157033,157130,158096,159026,159135,159244,160159,160727,161677,162275,163157,163399,163691,163889,164339,165038,165257,165407,165950,166916,167187,167562,168197,168638,168819,169070,169764,169813,170364,170531,170788,171105,172087,172312,173278,174088,174141,174743,174842,174846,175047,176028,176992,177204,178102,178236,179147,179983,180268,180724,181528,181803,182634,182793,183510,183523,183933,184345,184407,185088,185386,185425,186142,186424,187406,187810,187903,187939,187946,188138,188896,189822,190714,191437,191577,192088,192945,192997,193345,194206,194714,195585,195723,196064,196095,196950,197023,197184,198170,199024,199585,199590,200483,200762,201049,201925,202608,202707,203338,203747,203758,203867,204204,204826,205658,205854,205988,206397,207363,207565,207837,208313,208387,208797,209333,209439,210423,210751,211018,211708,211891,212719,213414,214209,215035,216017,216689,216919,217720,217743,218382,218913,219045,219740,219894,220577,221187,221195,221289,221867,222077,222162,222935,223219,223433,223743,223852,224051,224408,224784,225673,225933,226856,227442,227498,227968,228256,228704,229404,230212,230683,230742,231082,231686,232441,232655,232662,233028,233250,233351,234014,234165,235069,235506,235941,236060,236526,236790,237108,237932,238291,239218,239303,239587,239820,240679,241433,241673,241981,242155,242205,242985,243218,243327,243431,244419,244742,244853,244928,245192,246123,246580,246995,247831,248726,249296,250252,250614,251448,252441,253346,253540,254180,254889,255086,255959,256529,257480,257595,258473,259317,260200,260578,260657,261649,261850,261918,261954,262267,263128,263428,264391,264711,265146,265946,266880,266886,267362,267378,268218,268408,269330,270083,270913,271264,272215,272639,273560,274182,274440,275241,275709,275851,276749,277296,278149,278250,278584,279192,279606,280521,281430,281527,282481,282545,283161,284050,284120,284214,284838,285467,285470,286017,286400,286952,287570,287624,288319,288859,289536,290489,290550,290696,291510,292470,292882,293270,293332,294078,295074,295269,295931,296556,296848,297184,297873,298781,299007,299485,300206,301057,301883,302326,302444,303373,304369,305105,306088,306780,307776,308437,308803,308861,309387,309568,310305,311243,311812,312611,313016,313302,314015,314801,315712,316436,316560,316881,317515,317584,318383,318458,319378,320005,320524,321282,321558,322074,322288,322548,323475,323686,324327,324621,324891,325777,325972,325980,326525,327289,327816,328766,329535,329776,330232,330914,331880,332460,333182,333502,333871,334393,334507,334797,335665,336298,337065,337210,338078,339060,339185,339982,340176,340942,341034,341217,341870,342157,343067,343266,344037,344475,345343,345603,346001,346046,346988,347072,347697,348081,348204,348917,349824,350062,350067,350562,351433,351924,352284,353025,353499,353984,354242,354911,355881,355950,356802,357145,357221,357984,358246,358812,359732,359863,360689,360728,360904,361393,361516,362037,362910,363157,363392,363892,364096,365054,365769,366563,367014,367090,367345,368270,368550,369063,369377,369628,370211,371097,371691,372069,372719,373294,374238,374529,375236,376007,376337,376939,377918,378090,378932,379786,379924,380721,380795,381137,381893,382682,382820,383746,384611,385004,385576,386440,387066,387671,388505,389433,389925,390074,390381,391243,391967,392219,392373,392805,393547,393750,394504,395227,395602,396199,396496,397010,397124,397495,398351,398941,399103,399816,400333,401079,401905,402713,403325,403778,404193,404640,405022,405929,406525,407214,407984,408306,408966,409609,410082,410485,411331,411559,412404,412627,413172,413315,414052,414430,414945,415258,416226,416903,416931,417137,417561,418415,418430,419185,419212,419361,419565,419974,420750,421269,422086,422633,423474,423952,424862,424897,425497,426254,427235,427682,428381,428627,429217,429373,429998,430822,431292,431886,432388,432605,433124,433770,434560,434814,434935,435752,436155,436199,437144,437324,437888,438651,439098,439223,439465,439542,439702,440263,440816,440959,440968,441222,441330,441930,442059,442792,442936,443254,443302,443949,444484,444770,444783,444828,445368,446220,446801,447745,448642,449169,450012,450474,450484,450494,451081,452051,452138,452605,453138,453779,454108,454650,455264,455701,456562,457305,457477,457484,457547,458485,458858,459175,459400,459505,459587,460353,461310,461973,462403,463258,464168,465160,465197,465836,465840,466465,467076,467885,467978,468123,468574,468715,469121,469187,469765,470034,470563,471032,472026,472337,472745,473113,473741,474094,474286,474715,475553,475703,476515,477502,478227,478950,479930,480692,481055,482039,482146,482839,483353,484271,485109,486074,486134,486380,487131,487770,488004,488004,488831,489060,489371,490326,490642,491300,491609,491836,491925,492791,492887,493788,494642,495463,495807,496642,496946];
A=[427,541,131,122,56,51,679,740,829,230,796,582,769,459,629,64,170,976,522,973,420,322,768,769,433,880,478,160,88,163,632,620,679,977,213,138,712,184,536,818,253,923,901,426,947,360,679,148,238,451,282,110,364,906,293,763,367,226,462,718,19,708,450,263,565,819,64,842,79,379,808,696,972,265,297,411,718,693,241,588,832,832,748,616,754,961,700,243,747,306,520,49,559,985,159,493,593,851,705,895,839,777,517,502,90,604,713,422,428,621,974,161,631,316,185,832,678,726,560,656,152,232,96,173,284,441,727,828,929,800,249,480,117,806,706,326,54,119,136,914,439,40,488,584,926,173,878,434,838,724,171,460,833,41,1,829,944,940,108,762,337,473,354,599,250,45,408,217,477,903,684,277,763,143,311,630,707,559,684,219,711,74,632,556,475,320,919,231,485,265,280,689,752,560,807,99,143,180,409,306,968,729,703,820,422,64,391,458,758,642,107,588,5,192,654,254,323,485,119,781,304,598,114,517,836,274,973,1,208,773,43,329,703,439,858,753,363,120,235,688,395,907,954,208,88,151,599,428,510,467,346,417,777,774,890,950,374,890,698,25,522,149,856,169,338,417,501,753,463,141,170,21,928,759,27,527,829,861,73,554,258,514,455,346,786,862,79,701,5,88,324,170,947,174,80,945,32,962,205,335,898,456,312,47,512,858,61,542,764,956,56,711,915,330,799,900,160,389,527,627,186,598,278,310,544,573,936,930,616,268,204,141,940,386,122,903,286,11,485,793,480,921,753,365,922,828,833,884,938,850,915,817,839,640,516,711,632,42,61,497,110,368,817,782,952,786,488,398,158,127,694,633,204,45,649,873,658,276,337,724,531,253,757,326,703,193,328,727,524,621,677,674,884,828,331,632,485,63,350,677,403,910,98,172,321,795,868,270,714,812,940,862,142,958,116,682,938,183,788,674,504,269,234,953,650,860,844,91,826,947,880,795,740,501,223,36,865,453,52,822,142,127,173,906,106,383,148,213,352,640,453,848,530,852,820,715,311,284,273,834,343,130,912,946,512,486,463,839,391,690,851,558,554,138,31,818,719,687,75,352,405,543,745,569,579,85,691,493,245,85,596,568,308,878,712,490,463,472,602,579,305,232,197,910,660,772,510,207,515,555,775,470,882,406,651,218,497,363,294,415,31,911,506,607,262,919,399,64,857,727,927,165,366,683,439,122,692,568,575,509,281,663,864,391,319,234,735,360,595,679,53,319,226,195,827,321,67,280,471,358,173,682,339,701,718,437,348,679,43,259,865,420,166,624,136,359,10,742,373,77,286,1,751,331,126,671,16,899,261,534,936,106,575,546,186,757,142,510,103,900,275,107,8,143,838,920,742,812,699,911,317,387,835,143,809,844,141,636,490,367,791,122,908,147,600,196,449,545,900,259,321,638,476,125,224,480,427,213,504,787,358,796,45,847,819,641,114,332,901,868,400,368,647,68,438,907,526,115,812,553,198,350,2,248,622,499,348,457,874,577,184,399,912,296,864,672,577,51,521,740,213,796,795,301,265,428,10,273,343,212,490,649,382,571,169,370,682,564,783,423,281,527,402,431,810,581,150,844,170,249,671,682,218,17,465,533,613,489,220,821,302,142,426,399,752,876,102,343,497,700,454,703,661,604,600,374,470,459,917,431,301,296,869,722,653,463,90,568,237,10,205,550,887,400,270,13,622,687,241,675,657,37,706,438,166,316,255,428,861,616,222,36,736,733,254,849,195,273,45,809,623,203,92,22,84,127,293,39,488,761,853,878,903,123,236,195,641,356,807,301,395,634,409,710,79,465,702,640,413,751,632,681,326,39,840,142,710,404,470,617,441,249,854,361,224,890,3,152,110,26,278,337,767,25,323,879,542,335,594,620,186,776,211,465,305,881,505,516,135,47,326,31,703,527,328,750,662,278,430,526,138,606,216,396,387,377,682,278,858,747,5,866,365,444,92,100,601,713,79,485,405,805,438,409,585,178,482,340,297,207,615,425,626,297,702,67,334,602,276,541,331,301,741,696,70,670,457,639,790,274,423,614,784,314,531,155,367,93,286,725,297,749,720,666,374,534,427,671,865,552,859,505,603,220,601,583,509,640,828,876,713,107,580,400,17,238,861,203,792,275,682,407,520,452,353,814,42,579,747,855,643,178,503,372,149,266,171,339,774,170,504,703,183,217,643,154,729,106,677,444,806,193,877,834,449,310,374,406,47,547,438,838,550,169];